We consider a class of routing algorithms for communication networks called Ant-Based Routing Algorithms (ARA), that are inspired by experimental observations of ant colonies in nature. It was found that ant colonies are able to "discover" the shorter of two paths to a food source by laying and following "pheromone trails". This idea has been adapted for purposes of routing in communication networks, whereby probe packets (analogues of ants) are used to explore the network and collect measurements of path delays. These measurements help create analogues of pheromone trails, which then influence the node routing tables. We study an ARA algorithm that adapts probabilistic node routing tables based on estimates of path delays. We consider wireline, packet-switched networks. Using methods from the theory of adaptive algorithms and stochastic approximation, we provide convergence results, and study the equilibrium behavior of the routing algorithm.

  Punyaslok Purkayastha is a post-doctoral researcher in the Department of Electrical and Computer Engineering , University of Maryland College Park . Purkayastha completed Ph.D. dissertation work here, under the guidance of Prof. John S. Baras .